package class3;

import common.ListNode;
import common.ListNodeUtils;

/**
 * https://leetcode.cn/problems/LGjMqU/description/
 * 重排链表
 * 解题思路:
 * 1.找到链表中间节点,
 * 2.反转后半端链表,断开链表
 * 3.交叉合并 *
 */
public class Code27_ReorderList {
    public static void main(String[] args) {
        ListNode head = ListNodeUtils.getLinked(1, 2, 3, 4, 5, 6);
        reorderList(head);
        ListNodeUtils.print(head);
    }

    public static void reorderList(ListNode head) {
        // 双指针获取 中间节点
        ListNode mid = getMid(head);
        // 反转后半段链表
        ListNode newHead = reverse(mid.next);
        // 断开链表
        mid.next = null;
        /**
         * 交叉合并过程
         * p1:1-2-3
         * p2:6-5-4
         * 第一步: next = 5-4
         * 第二步: 6-2-3
         * 第三步: 1-6-2-3
         * 第四步: p1 = p2.next; 也就是 2 (p2.next)
         * 第五步: p2 = next;  也就是刚刚预先存储的 5-4的头节点
         */
        ListNode p1 = head, p2 = newHead;
        while (p1 != null && p2 != null) {
            ListNode next = p2.next;
            p2.next = p1.next;
            p1.next = p2;
            p1 = p2.next;
            p2 = next;
        }
    }

    public static ListNode getMid(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }

    public static ListNode reverse(ListNode head) {
        ListNode pre = null;
        while (head != null) {
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}
